from cmath import inf
from typing import Optional

from python.mypackage import TreeNode


class Solution:
    """
    方法： maxPathSum 使用DFS计算二叉树中的最大路径和
    
    Args:
        root (Optional[TreeNode]): 二叉树的根节点
        
    Returns:
        int: 二叉树中任意路径的最大路径和
        
    Time:  
        O(N)，其中 N 为二叉树的节点数。每个节点只会被访问一次。
        
    Space:  
        O(H)，其中 H 为二叉树的高度。递归调用的栈空间取决于二叉树的高度。
    """
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        ans = -inf
        def dfs(node):
            if node is None:
                return 0
            l_val = dfs(node.left)
            r_val = dfs(node.right)
            nonlocal ans
            ans = max(ans, l_val + r_val + node.val)
            return max(max(l_val, r_val) + node.val, 0)
        dfs(root)
        return ans